package com.example.leetcode.treecode;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> out = new LinkedList<>();
        if (root == null) {
            return out;
        }
        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode last = stack.pollLast();
            out.add(last.val);
            if (last.right != null) {
                stack.add(last.right);
            }
            if (last.left != null) {
                stack.add(last.left);
            }
        }

        return out;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }

        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pollLast();
            output.addFirst(node.val);
            if (node.left != null) {
                stack.add(node.left);
            }
            if (node.right != null) {
                stack.add(node.right);
            }
        }
        return output;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        LinkedList<Integer> out = new LinkedList<>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            out.add(curr.val);
            curr = curr.right;
        }
        return out;
    }

    public static void main(String[] args) {
        // 初始节点
        //           1
        //       2        3
        //    4     5
        TreeNode root1 = new TreeNode(1);
        TreeNode root2 = new TreeNode(2);
        TreeNode root3 = new TreeNode(3);
        TreeNode root4 = new TreeNode(4);
        TreeNode root5 = new TreeNode(5);
        root1.left = root2;
        root1.right = root3;
        root2.left = root4;
        root2.right = root5;
        // 前序遍历 [1, 2, 4, 5, 3]
//        List<Integer> integers = new Solution1().preorderTraversal(root1);
//        List<Integer> integers = new Solution().postorderTraversal(root1);
//        System.out.println(integers);
    }
}
